package video.simple100;

import org.junit.Test;

/**
 * 53. 最大子序和
 */
public class LeetCode53 {

    @Test
    public void test() {
        int[] nums = {-1000, 10000};
        System.out.println(maxSubArray(nums));
    }


    /**
     * 解题思路
     * 循环  +  内循环， 依次求和，每次的和 和 上一次的和进行一个判断， 谁大最后就返回谁的值
     * 1 个数也算一个子序
     *
     * @param nums
     * @return
     */
    public int maxSubArray(int[] nums) {
        //  -2, 1, -3, 4, -1, 2, 1, -5, 4
        //  -2
        //  -2   1
        //  -2   1,  -3,
        //  -2   1,  -3, 4,
        //  -2   1,  -3, 4, -1,
        //  -2  ..................
        int maxNum = nums[0];
        for (int i = 0; i < nums.length; i++) {
            int zNum = nums[i];
            for (int j = i + 1; j < nums.length; j++) {
                zNum += nums[j];
                if(zNum > maxNum){
                    maxNum = zNum;
                }
                // 1 个数也算一个子序判断
                if(nums[j] > maxNum){
                    maxNum = nums[j];
                }
            }
        }
        return  maxNum;
    }
}
